/**
 * @author ChaP
 * @date 2019/05/16
 * @describe:
 */
package CodingTest.AC20190516;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * leetcode - 430
 * 您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

 扁平化列表，使所有结点出现在单级双链表中。您将获得列表第一级的头部。



 示例:

 输入:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

 输出:
 1-2-3-7-8-11-12-9-10-4-5-6-NULL

 */
public class flatten {
    class Node{
        public int val;
        public Node prev;
        public Node next;
        public Node child;
        public Node(){}

        public Node(int _val,Node _prev,Node _next,Node _child){
            val = _val;
            prev = _prev;
            next = _next;
            child = _child;
        }
    }
    public Node flattern(Node head){
        if(head == null) return null;
        Stack<Node> stack = new Stack<Node>();
        Node cur = head;
        while(cur.next!=null || cur.child != null || !stack.isEmpty()){
            if(cur.child !=null){
                if(cur.next != null){
                    stack.push(cur.next);
                }
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
            }
            if(cur.next == null&&cur.child==null&&!stack.isEmpty()){
                Node temp = stack.pop();
                cur.next = temp;
                temp.prev = cur;
            }
            cur = cur.next;

        }
        return head;

    }

}
